﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
// 原题连接：https://leetcode.cn/problems/count-negative-numbers-in-a-sorted-matrix/
/*
题目描述：
给你一个 m * n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非递增顺序排列。 请你统计并返回 grid 中 负数 的数目。

示例 1：
输入：grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
输出：8
解释：矩阵中共有 8 个负数。

示例 2：
输入：grid = [[3,2],[1,0]]
输出：0
 

提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 100
-100 <= grid[i][j] <= 100

进阶：你可以设计一个时间复杂度为 O(n + m) 的解决方案吗？
*/

// 方法1——暴力法
/*
思路：
直接遍历矩阵中所有的元素，用一个变量count来记录矩阵中负数的个数，
当grid[i][j] < 0时，就让count++;
最后返回count即可。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
int countNegatives1(int** grid, int gridSize, int* gridColSize) {
    assert(grid && gridColSize);
    int i = 0;
    int j = 0;
    int count = 0;
    for (i = 0; i < gridSize; i++) {
        for (j = 0; j < *gridColSize; j++) {
            if (grid[i][j] < 0) {
                count++;
            }
        }
    }
    return count;
}
// 时间复杂度：O(nm)，n和m分别为矩阵的函数和列数。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。

// 方法2——二分查找法
/*
思路：
根据题目描述，我们可以在每一行使用二分法找到第一个小于0的元素，记其坐标为pos
则这一行的负数个数为col - pos。
我们用一个变量count来记录矩阵中负数的个数，每次都让count += col - pos。
最后返回count即可。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
int countNegatives2(int** grid, int gridSize, int* gridColSize) {
    assert(grid && gridColSize);
    int i = 0;
    int left = 0;
    int right = 0;
    int mid = 0;
    int count = 0;
    for (i = 0; i < gridSize; i++) {
        left = 0;
        right = *gridColSize - 1;
        while (left <= right) {
            if (grid[i][left] < 0) {
                count += *gridColSize - left;
                break;
            }
            mid = left + (right - left) / 2;
            if (grid[i][mid] < 0) {
                right = mid;
            }
            else {
                left = mid + 1;
            }
        }
    }
    return count;
}
// 时间复杂度：O(nlogm)，n和m分别为矩阵的行数和列数。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。

int main() {
    int arr[][4] = { {4,3,2,-1},{3,2,1,-1},{1,1,-1,-2},{-1,-1,-2,-3} };
    int result = countNegatives2(arr, 4, 4);
    printf("%d", result);
    return 0;
}

